package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;
import com.lun.util.SinglyLinkedList.ListNode;

public class LinkedListInBinaryTree {
    
	//方法一：自己写的，DFS + 暴力算法
	public boolean isSubPath(ListNode head, TreeNode root) {
    	if(root == null) return false;
        return helper(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    
	private boolean helper(ListNode head, TreeNode root) {
		if(head != null && root == null)
			return false;
		
		if(head != null && root != null) {
			if(head.val != root.val)
				return false;
			return helper(head.next, root.left) || helper(head.next, root.right);
		}
		return true;
	}
	
	
	//方法二：自己写的，KMP + DFS
	public boolean isSubPath2(ListNode head, TreeNode root) {
		int[][] patternAndNext = getPatternAndNext(head);
		return helper(patternAndNext, root, -1);
	}
	
	private boolean helper(int[][] patternAndNext, TreeNode node, int j) {
		if(node == null) return false;

		int[] pattern = patternAndNext[0], next = patternAndNext[1];
		while(j >= 0 && node.val != pattern[j + 1])
			j = next[j];
		if(node.val == pattern[j + 1])
			j++;
		if(j == patternAndNext[0].length - 1)
			return true;
		
		return helper(patternAndNext, node.left, j) || helper(patternAndNext, node.right, j);
	}
	
	//KMP算法
	private int[][] getPatternAndNext(ListNode head){
		int count = 0;
		ListNode p = head;
		
		while(p != null) {
			count++;
			p = p.next;
		}
		
		int[] pattern = new int[count]; 
		p = head;
		count = 0;
		while(p != null) {
			pattern[count++] = p.val;
			p = p.next;
		}
		
		int[] next = new int[count];
		
		//正戏
		int j = -1;
		next[0] = j;
		for(int i = 1; i < pattern.length; i++) {
			while(j >= 0 && pattern[i] != pattern[j + 1])
				j = next[j];
			if(pattern[i] == pattern[j + 1])
				j++;
			next[i] = j;
		}
		return new int[][] {pattern, next};
	}
	
	//方法三：别人写的，DFS + 暴力算法
    public boolean isSubPath3(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        return head.val == root.val && (dfs(head.next, root.left) || dfs(head.next, root.right));
    }
	
    //方法四：别人写的，KMP + DFS
    public boolean isSubPath4(ListNode head, TreeNode root) {
        List<Integer> A = new ArrayList<>(), dp = new ArrayList<>();
        A.add(head.val);
        dp.add(0);
        int i = 0;
        head = head.next;
        while (head != null) {
            while (i > 0 && head.val != A.get(i))
                i = dp.get(i - 1);
            if (head.val == A.get(i)) ++i;
            A.add(head.val);
            dp.add(i);
            head = head.next;
        }
        return dfs(root, 0, A, dp);
    }

    private boolean dfs(TreeNode root, int i, List<Integer> A, List<Integer> dp) {
        if (root == null) return false;
        while (i > 0 && root.val != A.get(i))
            i = dp.get(i - 1);
        if (root.val == A.get(i)) ++i;
        return i == dp.size() || dfs(root.left, i, A, dp) || dfs(root.right, i, A, dp);
    }
	
}
